package com.lisp.algorithm.leetcode;

public class Q198 {

	public static void main(String args[]) {
		
		int nums[] = {1};
		System.out.println(rob(nums));
		
		nums = new int[]{1, 2};
		System.out.println(rob(nums));
		
		nums = new int[]{1, 2, 1};
		System.out.println(rob(nums));
	
		nums = new int[]{1, 2, 4, 8};
		System.out.println(rob(nums));
		
		nums = new int[]{1, 2, 4, 8, 20};
		System.out.println(rob(nums));
	}
	
	public static int rob(int nums[]) {
		int dp[] = new int[nums.length + 1];
		dp[0] = 0;
		dp[1] = nums[0];
		
		// false 代表选择i-1； true表示选择i-2, 此时nums[i-1]被选中
		boolean[] dpRoute = new boolean[nums.length + 1];
		dpRoute[0] = false;
		dpRoute[1] = true;
		
		// f(i) = max {f(i-1), f(i-2) + nums[i-1]}
		for(int i=2; i<=nums.length; i++) {
			if(dp[i-1] > dp[i-2] + nums[i-1]) {
				dpRoute[i] = false;
				dp[i] = dp[i-1];
			} else {
				dpRoute[i] = true;
				dp[i] = dp[i-2] + nums[i-1];
			}
		}
		
		int j=nums.length;
		while(j>0) {
			if(dpRoute[j]) {
				System.out.println("索引：" + (j-1) + "，数值：" + nums[j-1]);
				j = j - 2;
			} else {
				j = j - 1;
			}
		}
		
		return dp[nums.length];
	}
}
